package org.raymond.iworks.study.basic.algorithm.common;

/**
 * 分治算法最佳实践-汉诺塔问题
 * 汉诺塔的传说:
 * 汉诺塔问题源于印度一个古老传说的益智玩具.大梵天创造世界的时候做了三根金刚石柱子,在一根
 * 柱子上从下往上按照大小顺序摞着64片黄金圆盘.大梵天命令婆罗门把圆盘从下面开始按照大小顺序
 * 重新摆放在另一根柱子上。并且规定,在小圆盘上不能放大圆盘,在三根柱子之间一次只能移动一个圆盘.
 *
 * 假如每秒一次,共需多长时间?
 *
 * 思路分析:
 * 1) 如果只有一个盘,A->C
 * 2) 如果n>=2,总是可以看作是两个盘(1,最下边的盘;2,其他所有盘)
 * 2.1) 先把最上面的盘 A->B
 * 2.2) 把最下边的盘  A->C
 * 2.3) 把B塔的所有盘 B->C
 *
 * 注:即利用分治算法的模式,将n个盘分解为两个盘(上面n-1个盘和最下面的1个盘),通过递归深入到
 * 最后只有1个盘的情况,且过程中B塔与C塔的盘不断交换位置.
 */
public class Hanoitower {
    public static void main(String[] args) {
        hanoiTower(5, 'A', 'B', 'C');
    }

    /**
     * 汉诺塔的移动方法
     * 使用分治算法
     * @param num
     * @param a
     * @param b
     * @param c
     */
    public static void hanoiTower(int num, char a, char b, char c){
        if(num==1){
            System.out.println("第1个盘从 "+a+"->"+c);
        }else{
            // 如果我们有n>=2的情况,总是可以看作是两个盘:最下边的一个盘子,上面所有的盘
            // 1,先把最上面的所有盘A->B,移动过程会使用C
            hanoiTower(num-1, a, c, b);
            // 2,把最下边的盘 A->C
            System.out.println("第"+num+"个盘从 "+a+"->"+c);
            // 3,把B塔的所有盘 B->C, 移动过程使用到A塔
            hanoiTower(num-1, b, a, c);
        }
    }
}
